package sort

// 归并排序
func (this *Sort) MergeSort(arr []int) {
	// 获取切片长度
	length := len(arr)
	if length <= 1 {
		return
	}

	// 归并排序
	mergeSortSub(arr, 0, length-1)

	return
}

// 递归子函数
func mergeSortSub(arr []int, low int, high int) {

	if low >= high {
		return
	}

	mid := (low + high) / 2
	mergeSortSub(arr, low, mid)
	mergeSortSub(arr, mid+1, high)
	merge(arr, low, mid, high)
}

// 排序
func merge(arr []int, low int, mid int, high int) {

	// 初始化变量
	i, j, k := low, mid+1, 0
	tmp := []int{}

	for ; i <= mid && j <= high; k++ {
		if arr[i] < arr[j] {
			tmp[k] = arr[i]
			i++
		} else {
			tmp[k] = arr[j]
			j++
		}
	}

	// 左侧不为空
	for ; i <= mid; k++ {
		tmp[k] = arr[i]
	}

	// 右侧不为空
	for ; j <= high; k++ {
		tmp[k] = arr[j]
	}

	// 拷贝数组
	copy(arr[low:high+1], tmp)

	return
}
